package leetcode_1_200;

import node.Node;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_117 {
    public static void main(String[] args) {
        Node node = new Node(1, new Node(2, new Node(4), new Node(5), null),
                new Node(3, null, new Node(7), null), null);
        connect(node);
    }
    private static Node connect(Node root) {
        int depth = getDepth(root, 0);
        List<List<Node>> nodes = new ArrayList<>(depth);
        for (int i = 0; i < depth; i++) {
            nodes.add(new ArrayList<>());
        }
        f(nodes, root, 0);
        for (int i = 0; i < nodes.size(); i++) {
            for (int j = 0; j < nodes.get(i).size() - 1; j++) {
                nodes.get(i).get(j).next = nodes.get(i).get(j + 1);
            }
        }
        return root;
    }
    private static void f(List<List<Node>> nodes, Node node, int depth){
        if (node == null)
            return;
        nodes.get(depth).add(node);
        f(nodes, node.left, depth + 1);
        f(nodes, node.right, depth + 1);
    }
    private static int getDepth(Node node, int depth){
        if (node == null)
            return depth;
        return Math.max(getDepth(node.left, depth + 1), getDepth(node.right, depth + 1));
    }
}
